package kyssion.leetcode.num51_100;

public class code52_最大子序列和 {

    public static void main(String[] args) {
        System.out.println(new code52_最大子序列和().maxSubArray(
                new int[]{
                        -2,1,-3,4,-1,2,1,-5,4
                }
        ));
    }

    /**
     * 两种dp的思路
     *
     * 第一种,不需要额外数组的方法
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int maxNum = nums[0];
        int nowNum = nums[0];
        for (int a = 1; a < nums.length; a++) {
            if(nowNum+nums[a]>nums[a]){
                nowNum = nowNum+nums[a];
            }else{
                nowNum = nums[a];
            }
            maxNum = Math.max(nowNum,maxNum);
        }
        return Math.max(nowNum,maxNum);
    }

    /**
     * 额外数组辅助
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length]; //db[i]表示nums尾部到i的最大值

        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            if(dp[i] > max) {
                max = dp[i];
            }
        }

        return max;
    }
}
